//打家劫舍
public class Rob {
}
class RobSolution{
    int robList(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for(int i=1;i<n;i++){
            dp[i] = Math.max(dp[i-1],nums[i]);
            if(i>1)dp[i] = Math.max(dp[i-2]+nums[i],dp[i]);
            if(i>2)dp[i] = Math.max(dp[i-3]+nums[i],dp[i]);
        }
        return dp[n-1];
    }

    int robCircle(int[] nums) {
        int n = nums.length;
        if(n==1)return nums[0];
        int[] rob1 = new int[n-1];
        int[] rob2 = new int[n-1];
        for(int i=0;i<n-1;i++){
            rob1[i] = nums[i];
            rob2[i] = nums[i+1];
        }
        return Math.max(robList(rob1),robList(rob2));
    }

    int robTree(TreeNode root){
        int[] res = dfs(root);
        return Math.max(res[0],res[1]);
    }
    int[] dfs(TreeNode root){
        if(root==null)return new int[]{0,0};
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int[] res = new int[2];
        res[0] = Math.max(left[1],left[0])+Math.max(right[0],right[1]);
        res[1] = root.val+left[0]+right[0];
        return res;
    }
}